{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked List Reversal \n",
    "\n",
    "## Problem\n",
    "\n",
    "Write a function to reverse a Linked List in place. The function will take in the head of the list as input and return the new head of the list.\n",
    "\n",
    "You are given the example Linked List Node class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self,value):\n",
    "        \n",
    "        self.value = value\n",
    "        self.nextnode = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution\n",
    "\n",
    "Fill out your solution below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(head):\n",
    "    cur = head\n",
    "    pre, nxt = None, None\n",
    "    while cur:# watch out\n",
    "        nxt = cur.nextnode\n",
    "        cur.nextnode = pre\n",
    "        pre = cur\n",
    "        cur = nxt\n",
    "    return pre #watch out\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "**Note, this isn't a classic run cell for testing your solution, please read the statements below carefully**\n",
    "\n",
    "You should be able to easily test your own solution to make sure it works. Given the short list a,b,c,d with values 1,2,3,4. Check the effect of your reverse function and make sure the results match the logic here below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a list of 4 nodes\n",
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "d = Node(4)\n",
    "\n",
    "# Set up order a,b,c,d with values 1,2,3,4\n",
    "a.nextnode = b\n",
    "b.nextnode = c\n",
    "c.nextnode = d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's check the values of the nodes coming after a, b and c:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "print (a.nextnode.value)\n",
    "print (b.nextnode.value)\n",
    "print (c.nextnode.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'value'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-46-9ee2d814a788>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0md\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnextnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'value'"
     ]
    }
   ],
   "source": [
    "d.nextnode.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far so good. Note how there is no value proceeding the last node, this makes sense! Now let's reverse the linked list, we should see the opposite order of values!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x1067a2f28>"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "print (d.nextnode.value)\n",
    "print (c.nextnode.value)\n",
    "print (b.nextnode.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "Missing parentheses in call to 'print' (<ipython-input-49-42251ca948f9>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-49-42251ca948f9>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    print a.nextnode.value # This will give an error since it now points to None\u001b[0m\n\u001b[0m          ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m Missing parentheses in call to 'print'\n"
     ]
    }
   ],
   "source": [
    "print a.nextnode.value # This will give an error since it now points to None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, now we can see that each of the values points to its previous value (although now that the linked list is reversed we can see the ordering has also reversed)\n",
    "\n",
    "## Good Job!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
